/*
题目描述：给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/

*/

//使用前序遍历求解:（O(N),O(1)）
class Solution {
public:
// 采用前序遍历求节点个数
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        stack<TreeNode*> st;
        int num = 0;
        TreeNode* node = root;
        while(!st.empty() || node){
            while(node){
                st.emplace(node);
                node = node->left;
            }
            node = st.top();
            st.pop();
	//出栈(节点处理完)则可以进行数量累加
            num++;
            node = node->right;
        }
        return num;
    }
};

/*
也可以基于满二叉树和完全二叉树的性质来解题
首先判断该树是否是一颗满二叉树，如果是直接是用公式进行计算，否则先记录其最大深度
记录深度之后，进行层次遍历寻找第一个边界节点。边界节点的定义为第一个叶子节点或者只有左孩子的节点
找到之后可以继续利用公式进行计算
*/
//（O(N),O(1)）
class Solution {
public:
    // 优化的层次遍历
    int countNodes(TreeNode* root) {
        // 先求出树的深度depth, 并检验是否是一颗满二叉树
        if(root == nullptr ) return 0;
        int depth = 0;
        TreeNode* cur = root;
        while(cur){
            depth++;
            cur = cur->left;
        }
        cur = root;
        int deep =0;
        while(cur){
            deep++;
            cur = cur->right;
        }
        // 如果是一颗满二叉树直接计算其节点个数
        if(depth == deep) return pow(2,depth)-1;

        // 找到第一个叶子节点或者只有左孩子的节点
        queue<TreeNode*> que;
        que.push(root);
        int i=0;
        // 标记节点边界，
        // 边界条件为碰到一个节点是叶子节点或者该节点只有左孩子
        bool flag = true;
        while(!que.empty()){
            size_t size = que.size();
            // 标记是否找到叶节点，因为后面的break只能退出一层循环
            bool end = false;
            for(i=0;i<size;i++){
                TreeNode* node = que.front();
                que.pop();
                // 该节点的左右子节点均为空，说明也是个叶子节点，找到满足条件的边界
                if(node->left==nullptr && node->right==nullptr){
                    end = true;
                    break;
                }
                // 此时的边界是只有左孩子的节点
                else if(node->right==nullptr){
                    end = true;
                    flag = false;
                    break;
                }
                // 没遇到边界，继续层次遍历
                else{
                    que.push(node->left);
                    que.push(node->right);
                } 
            }
            if(end) break;
        }
        int temp = pow(2,depth-1)-1+2*(i);
        // falg为真表示最后一个节点是左右孩子为空，否则就是只有左孩子的节点
        int num = flag ? temp : temp+1;
        return num;
    }
};

// 递归版本1（O(logN*logN),O(logN)）
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftHeight++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightHeight++;
        }
		// 是一颗满二叉树
        if (leftHeight == rightHeight) {
            return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
        }
		// 不是满二叉树
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

// 递归版本2（O(N),O(logN)）
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        return countNodes(root->left)+countNodes(root->right)+1;
    }
};
